﻿#define _CRT_SECURE_NO_WARNINGS 1

// NC316 体育课测验(二)

//描述
//体育课共有numProject个考核项目，编号为
//0 到 numProject − 1，考核中每两个项目被划分为一组得到分组数组groups[i]，现规定若想完成项目
//groups[i][0]，必须先完成groups[i]​[1]。保证所有分组互不相同，若分组情况能顺利完成考核，请返回任意的一个完成顺序, 否则返回空数组 。
//数据范围：
//1 ≤ numProject ≤ 2000
//1 ≤ groups[i].length ≤ numProject ∗ (numProject−1)
//示例1
//输入：
//3, [[2, 1]]
//返回值：
//[1, 2, 0]
//
//说明：
//要先完成1号项目，再完成2号项目，而0号项目不受约束，故可以以1 2 0的顺序完成项目。
//示例2
//输入：
//3, [[1, 0], [0, 1]]
//
//返回值：
//[]
//
//说明：
//第一个分组要求先完成0号项目，再完成1号项目；而第二个分组要求先完成1号项目，再完成0号项目，自相矛盾，故不可以完成项目。



// 拓扑排序
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;

class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numProject int整型
     * @param groups int整型vector<vector<>>
     * @return int整型vector
     */
    vector<int> findOrder(int numProject, vector<vector<int> >& groups)
    {
        unordered_map<int, vector<int>> edges;//邻接表
        vector<int> in(numProject);//入度
        //建图
        for (auto& e : groups)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);//b->a
            in[a]++;//a的入度+1
        }

        //入度为0入队列
        queue<int> q;
        for (int i = 0; i < numProject; i++)
        {
            if (in[i] == 0) q.push(i);
        }

        //拓扑排序
        vector<int> ret;
        while (q.size())
        {
            int t = q.front();
            q.pop();
            ret.push_back(t);
            for (auto e : edges[t])
            {
                //t->e
                if (--in[e] == 0) q.push(e);
            }
        }

        if (ret.size() == numProject) return ret;
        else return {};
    }
};